package com.leetcode.dynamic_programming.zero_one_backpack;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/20 11:31
 */
public class SumEqual_416 {

    // 一定要按照题目要求，要求boolean，建立的状态方程也应该是boolean的
    public boolean canPartition(int[] nums) {
        if (nums.length == 0) return true;
        int sum = Arrays.stream(nums).sum();
        // 不能被2整除，肯定为false
        if ((sum & 1) == 1) return false;
        sum >>= 1;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = num; i <= sum; i++) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[sum];
    }

    static class Solution {
        public boolean canPartition(int[] nums) {
            int sum = Arrays.stream(nums).sum();
            if ((sum & 1) == 1) return false;
            sum /= 2;
            int len = nums.length;
            boolean[][] dp = new boolean[len + 1][sum + 1];
            for (int i = 0; i <= len; i++) {
                dp[i][0] = true;
            }
            for (int i = 1; i <= len; i++) {
                for (int j = sum; j >= 1; j--) {
                    if (j >= nums[i - 1])
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            return dp[len][sum];
        }

        // 状态压缩
        public boolean canPartitionBetter(int[] nums) {
            int sum = Arrays.stream(nums).sum();
            if ((sum & 1) == 1) return false;
            sum >>= 1;
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            for (int num : nums) {
                // 对于2维数组来说，正反遍历都可以
                // 对于1维数组而言，必须要反向遍历，保证上一轮遍历的结果不影响这一轮的
                for (int j = sum; j >= num; j--) {
                    dp[j] = dp[j] || dp[j - num];
                }
            }
            return dp[sum];
        }
    }

}
